Locality of Reference

Locality of Reference

The key to good cache performance is to maintain strong locality of reference. This can be restated as a rule of thumb: "Keep things that are used together, close together." Or, "Extract the greatest possible use from any 128-byte cache line before touching another." You must decide how to apply these principles in the context of your program design. Some possible techniques:

When designing a large data structure, group small fields together at one end of the structure. Do not mix small and large fields.
Consolidate frequently-tested switches, flags, and pointers into a single record so they will tend to stay in cache.
Avoid searching linked lists of structures. Each time a process visits a link merely to find the address of the next link, it is likely to incur a cache miss. Worse, a search over a long list fills the cache with unneeded links, driving out useful data.
Avoid striding through a large array of structures (such as an array of graphics library objects), visiting only one or two fields in each structure. Whenever possible, arrange the data so that any sequential scan will visit and use every byte before moving on.
Use inline function definitions for functions that are called within innermost loops. Do not use inline definitions indiscriminately, however, because they increase the total size of the binary, potentially causing more cache misses in non-looping code.
Use memalign() to allocate important structures on 128-byte boundaries, so as to ensure the structures fit in the smallest number of cache lines (see the memalign(3) reference page).